﻿#include <iostream>
#include <vector>
#include <string>

using std::vector;
using std::string;
using std::endl;
using std::cout;
using std::cin;

enum  MemType
{
	F,
	U,
	N
};

enum  Function
{
	A,
	ALLOC,
	FREE,
	SHOW,
	NEATEN,
};

struct MemInfo
{
	MemInfo()
	{}
	MemInfo(int b, int e)
	{
		begin = b;
		end = e;
		type = F;
	}

	int size()
	{
		return end - begin;
	}
	MemType type;
	int begin;
	int end;
};

class MemPool
{
public:
	MemPool()
	{
		total = 500;
		cur_size = 0;
		number = 0;
		ptr = (char*)malloc(total);
	}

	~MemPool()
	{
		free(ptr);
	}

	void PrintMenu()
	{
		printf("**********1.分配空间*************\n");
		printf("**********2.释放空间*************\n");
		printf("**********3.查看使用情况*********\n");
		printf("**********4.空间整理*************\n");
	}

	void Process()
	{
		int select = 0;
		PrintMenu();
		while (true)
		{
			std::cout << "请选择：";

			cin >> select;
			switch (select)
			{
			case ALLOC:
				AllocMem();
				break;
			case FREE:
				FreeMem();
				break;
			case SHOW:
				ShowUesage();
				break;
			case NEATEN:
				NeatenMem();
				break;

			default:
				std::cout << "选择错误，重新输入" << std::endl;
			}

		}
	}

	void AllocMem()
	{
		// 空间大小 包含 \0
		std::cout << "数据以字符串存储，大小包含\\0,输入分配空间大小：";
		int sz;
		cin >> sz;

		std::cout << "输入选择存储的数据：";
		string str;
		getchar();// 清空'\n'
		std::getline(std::cin, str);
		// 数据合法性检测
		if (str.size() + 1 > sz)
		{
			std::cout << "存储数据大小不匹配，存储失败" << endl;
			mems.pop_back();
			return;
		}

		// 拷贝存储
		// 1.先找已存在的 N 块信息
		bool flag = false;
		for (int i = 0; i < mems.size(); i++)
		{
			if (mems[i].type == N && mems[i].size() >= sz)
			{
				// 使用该块信息
				int dif = mems[i].size() - sz;
				int b = mems[i].begin;
				for (int i = 0; i < str.size(); i++)
				{
					ptr[b + i] = str[i];
				}
				ptr[b + str.size()] = '\0';
				mems[i].end = b + sz;
				mems[i].type = U;

				// 该块后面的数据信息往前挪动
				// 并修改块信息
				b = mems[i + 1].begin;
				for (int k = i + 1; k < mems.size(); k++)
				{
					mems[k].begin -= dif;
					mems[k].end -= dif;
				}

				for (int k = b; k < cur_size; k++)
				{
					ptr[k - dif] = ptr[k];
				}
				flag = true;
				cur_size -= dif;
				break;

			}
		}
		// 2. 不存在符合的块信息，使用新的块
		if (!flag)
		{
			MemInfo mem;
			for (int i = 0; i < str.size(); i++)
			{
				ptr[cur_size + i] = str[i];
			}
			for (int i = str.size(); i < sz; i++)
			{
				ptr[cur_size + i] = '\0';
			}
			mem.begin = cur_size;
			mem.end = cur_size + sz;
			mem.type = U;
			mems.push_back(mem);
			// 更新下一次开辟空间的位置
			cur_size += sz;
			number++;

		}

	}

	void FreeMem()
	{
		cout << "输入你要释放的内存块编号：";
		size_t num;
		cin >> num;
		num--;
		if (num > mems.size())
		{
			cout << "输入编号无效" << endl;
		}
		mems[num].type = F;
		cout << "释放完成" << endl;
	}

	void ShowUesage()
	{
		// 展示 U F ，不展示N
		int sz = 0;
		int sum = 0;
		for (size_t i = 0; i < mems.size(); i++)
		{
			sz = mems[i].size();
			if (mems[i].type == U)
			{
				cout << sz << "U ";
				sum += sz;

			}
			else if (mems[i].type == F)
			{
				cout << sz << "F ";
			}
		}
		cout << total - sum << "F " << endl;
	}

	int GetNCount()
	{
		int sz = 0;
		for (int i = 0; i < mems.size(); i++)
		{
			if (mems[i].type == N)
			{
				sz++;
			}
		}
		return sz;
	}

	void MoveMem(int dif,int b)
	{
		for (int i = b; i < cur_size; i++)
		{
			ptr[i - dif] = ptr[i];
		}
	}

	void MoveMInfo(int dif,int b)
	{
		for (int i = b; i < mems.size(); i++)
		{
			mems[i].begin -= dif;
			mems[i].end -= dif;
			mems[i - 1] = mems[i];
			
		}
		mems.pop_back();
	}

	void NeatenMem()  
	{
		// mems中，如果有很多N块 未使用表明，这些N块太小了,需要将N块清理
		if (GetNCount() >= 2)
		{
			// 1. 清除mems[i]
			// 2. 将 mems[i].end 后面数据往前移动
			for (int i = 0; i < mems.size();)
			{

				if (mems[i].type == N)
				{
					int e = mems[i].end;
					int dif = mems[i].size();
					cur_size -= dif;
					MoveMInfo(dif, i + 1);
					MoveMem(dif, e);
				}
				else
					i++;
			}
		}
		else
		{
			// 将F块标记为N块
			for (int i = 0; i < mems.size(); i++)
			{
				if (mems[i].type == F)
				{
					mems[i].type = N;
				}
			}
		}

	}

private:
	vector<MemInfo> mems;
	char* ptr;
	int total;    // 全部空间大小
	int cur_size; //下次分配空间的起始地址
	int number; // num 对应 mems 下标

};

int main()
{

	MemPool mem;
	mem.Process();
	
	return 0;
}

